package cn.michael.dev.data.structure.linked.list;

import cn.michael.dev.entity.ListNode;

/**
 * Created by hufenggang on 2021/8/27.
 *
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 */
public class Leetcode876 {

    public ListNode middleNode(ListNode head) {
        ListNode firstNode = head;
        ListNode lastNode = head;

        if (head == null || head.next == null) {
            return head;
        }

        if (head.next.next == null) {
            return head.next;
        }

        while (lastNode.next.next != null) {
            firstNode = firstNode.next;
            lastNode = lastNode.next.next;
        }

        if (lastNode.next != null) {
            return firstNode.next;
        } else {
            return firstNode;
        }
    }
}
